# 二分搜索，在非降序序列a中搜索x
def binarySearch(a: list[int], x: int) -> int:
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if x > a[mid]:
            left = mid + 1 # x位于mid右边，调整左边界
        elif x < a[mid]:
            right = mid - 1 # x位于mid左边，调整右边界
        else:
            return mid # 找到x，返回当前位置
    return -1 # 搜索完毕，未找到x，返回-1

